package main

import "fmt"

//https://leetcode.cn/problems/maximum-subarray/description/

func main() {
	fmt.Println(maxSubArray([]int{-2, 1, -3, 4, -1, 2, 1, -5, 4}))
}

func maxSubArray(nums []int) int {
	res := nums[0]
	pre := 0
	for i := 0; i < len(nums); i++ {
		pre = max(pre+nums[i], nums[i])
		res = max(res, pre)
	}
	return res
}

func max(num1, num2 int) int {
	if num1 > num2 {
		return num1
	}
	return num2
}
